Tracking moving targets, even with a mobile observer robot, raises numerous challenges. These challenges become increasingly difficult to solve when the moving target's trajectory is unknown and the mobile observer robot has no prior knowledge of the workspace through which it and the target are moving.
FIG. 1 illustrates an observer robot 103 following a moving target 101 through a workspace 100. The observer robot 103 includes a sensor that provides it with a localized visibility region 109 of the workspace 100. The observer robot 103 has no prior knowledge of the workspace 100 or the target's trajectory. Accordingly, the observer robot 103 wants to keep the target 101 within the visibility region 109 in order to track changes in the target's movement. Complicating the observer robot's task are various obstacles 105, 111 and occlusions produced by those obstacles. If the target 101 interposes one of these obstacles 105, 111 or an occlusion between itself and the observer robot 103, then the observer robot 103 will not be able to identify the target 103 in the visibility region 109 and will likely lose track of the target 101 altogether. While the workspace 100 is shown in FIG. 1 as a bounded area, the workspace 100 is theoretically unbounded.
FIG. 2 illustrates a problem that arises when the tracking algorithm used by the observer robot 103 employs only visual servoing to follow the target 101. Sensors associated with the observer robot produce visibility regions 109a-109c. The observer robot 103 identifies the target 101 in each of the visibility regions 109a-109c and moves progressively from location 103a to location 103c as the target moves from location 101a to 101c. However, as the target 101 approaches an edge of obstacle 111, the target's trajectory passes behind the edge to location 101d. From visibility region 109d, the observer robot 103 will not be able to identify the target 101 due to the edge of obstacle 111. Accordingly, the observer robot's visual servoing control will not know what steering command to next render to the observer robot 103. Thus, the observer robot 103 will likely lose track of the target 101 unless the target's trajectory just happens to take it past the interposing obstacle 111.
The tracking problem presented in FIG. 2 somewhat resembles the problem that a large hauling truck faces while trying to round a corner without passing over the curb of the near-side street. However, in the example provided in FIG. 2, the observer robot 103 cannot see through the obstacle 111 and cannot pass over it either. Accordingly, pure visual servoing does not provide an appropriate solution for workspaces like the workspace 100.
Tracking problems have been encountered in various other disciplines. However, avoiding occlusions are not typically a concern of the tracking solution. For instance, missile control systems do not typically need to solve occlusion problems. Similarly, tracking targets through obstacles in known environments is not typically a major problem. If the observer robot has a priori knowledge of the workspace, it can react to trajectories selected by the target. For instance, the prior art includes solutions to problems known as “guarding the art gallery” in which a target having an unknown trajectory moves through a workspace (e.g., an art gallery) similar to that shown in FIG. 1. In this problem, fixed sensors at various locations in the workspace are used to track the moving target. In this problem's formulation, the fixed sensors typically have knowledge of the workspace and knowledge about the location of the other fixed sensors. Similarly, if the observer robot has a prior knowledge of the target's trajectory, it can plan for the target's movements and is less reliant upon sensor data. Prior knowledge even allows solutions to be developed off-line and even outside the observer robot using more powerful computing devices than those likely to be available in a small robot.
Similarly, on-line game-theoretic planning solutions involve preparing probabilistic models of a target's behavior and typically include prior knowledge of the workspace. However, such solutions are typically computationally intense and may not be suitable for implementation in many robotic applications.
Accordingly, a solution is needed for the problem of tracking targets having unknown trajectories through an unknown workspace by a mobile observer robot. The solution should be sufficiently elegant so as to minimize the impact on the computational resources of the mobile observer robot.